1. Field of the Invention
This invention relates to a content providing system, a user system, a tracing system, an apparatus, a method, and a program.
2. Description of the Related Art
In broadcast content delivery operations , the content of, e.g., television programs is encrypted and then delivered to users. The users decrypt the encrypted content with authorized decoders loaned by the distributor and watch the television programs from the obtained content. In broadcast content delivery operations, however, there are malicious authorized users (hereinafter, referred to as pirates) who clone decoders by copying the internal information (decryption key and the like) of an authorized decoder and enable encrypted content to be decrypted illegally.
As a deterrent to such piracy, various types of pirate identifying methods are known. Such pirate identifying methods are classified into two types: a first type includes methods based on a combinatorial construction and a second type includes methods based on an algebraic and number-theoretic construction.
A first pirate identifying method has the problem of having to make the transmission overhead very large to make sufficiently low the probability that an authorized user unrelated to the production of a cloned decoder (hereinafter, referred to as a pirate decoder) will be falsely detected as a pirate.
A second pirate identifying method has solved the above problem and achieved an efficient transmission overhead. Furthermore, in the second pirate identifying method, pirate identifying with revocation the decryption key of a specific user by applying a technique of secret sharing to a key distribution method has been proposed (e.g., see reference 1).
[Reference 1] M. Naor and B. Pinkas, “Efficient Trace and Revoke Schemes,” In Proc. of Financial Cryptography '00, LNCS 1962, Springer-Verlag, February, 2000, pp. 1-20.
However, a plurality of decryption keys or data which has a function equivalent to decryption keys can be stored in a pirate decoder in conspiracy between pirates. The pirate decoder might be subjected to black-box tracing. In black-box tracing, a pirate is identified by observing only the input and output of the pirate decoder without physically opening the decoder.
In this case, in the second pirate identifying method, the number of tests needed for black box tracing is exponential, which causes the problem of making black box tracing impractical. Specifically, a tracer who does black box tracing assumes a candidate for a pirate (hereinafter, referred to as a suspect) and checks whether the suspect's decryption key is held in the pirate decoder. The check is intended for all of the sets of possible suspects and is made on a set basis. The reason is that a single key generation polynomial f(x) is used as expressed by the following equation and therefore there is an upper limit to the number of decryption keys (the number of suspects) that can be revoked at a time:f(x)=a0+a1·x+a2·x2+ . . . +ak·xk 
If the total number of users is n and the maximum number of pirates in a coalition is k, such black box tracing requires as many suspect sets as nCk=n!/{k!(n−k)!} to be checked and therefore this is practically impossible as described above.
To overcome this problem, the technique for revoking decryption keys flexibly using a plurality of key generating polynomials (e.g., see reference 2). Here, “flexibly” means that there is no upper limit to the number of decryption keys that can be revoked.
[Reference 2] T. Matsushita, “A Flexibly Revocable Key-Distribution Scheme for Efficient Black-Box Tracing,” In Proc. of International Conference on Information and Communications Security '02, LNCS 2513, Springer-Verlag, December 2002, pp. 197-208.
In reference 2, however, since a technique of secret sharing has been applied to the key distribution method, the intention of each input (or an assumed suspect) is known by a pirate decoder during black box tracing. If the pirate decoder is ingenious, it reads the intention of the input and operates so as to prevent the pirate from being traced, thereby thwarting black box tracing. This raises the following problem: a pirate cannot be identified or an innocent user will be falsely charged.
As described above, in the conventional pirate identifying methods, when black box tracing is done, the intention of each input is known by a pirate decoder. This causes the following problem: an ingenious pirate decoder thwarts black box tracing.